Storage of secret information involves the risk of loss or destruction of the secret information and the risk of theft. The risk of loss or destruction can be reduced by storing a plurality of copies of the secret information. This, however, increases the risk of theft. One solution for eliminating these risks is a secret sharing scheme (SSS) (refer to non-patent literature 1 and 2, for example).
In the secret sharing scheme, a plurality of shares SH(1) to SH(N) are generated from secret information MSK and are managed separately by a plurality of share management apparatuses PA(1) to PA(N), and the secret information MSK can be reconstructed only when a predetermined number or greater of shares among the shares SH(1) to SH(N) are obtained. A typical method for the secret sharing scheme will be described next.
[(N, N) threshold secret sharing scheme]
In an (N, N) threshold secret sharing scheme, if all the shares SH(1) to SH(N) are given, the secret information MSK can be reconstructed, whereas if any (N−1) shares SH(φ1) to SH(φN−1) are given, the secret information MSK can never be obtained. An example will be given below.                SH1, . . . , SHN−1 are selected at random.        SHN=MSK−(SH1+ . . . +SHN−1) is calculated.        The shares SH1, . . . , SHN are managed separately by a plurality of share management apparatuses PA(1), . . . , PA(N).        If all the shares SH1, . . . , SHN are given, the secret information MSK can be reconstructed by the reconstruction processing represented as MSK=SH1+ . . . +SHN.        
The operation MSK=SH1+ . . . +SHN for reconstructing the secret information MSK from the shares SH1 to SHN is linear. If the reconstruction processing is performed with the results of the same linear operation CALC for individual shares, using the shares SH(1) to SH(N) and a value σ as operands, the results being shares SH′(1) to SH′(N), the result of the linear operation CALC using the secret information MSK and the value σ as operands can be obtained. If the reconstruction processing is executed with SH′(1)=σ·SH(1), . . . , SH′(N)=σ·SH(N) as the shares SH′(1), . . . , SH′(N), the following can be obtained, for example.
                                                                                                              σ                    ·                    S                                    ⁢                                                                          ⁢                                      H                    ⁡                                          (                      1                      )                                                                      +                …                +                                                      σ                    ·                    S                                    ⁢                                                                          ⁢                                      H                    ⁡                                          (                      N                      )                                                                                  =                            ⁢                              σ                ·                                  (                                                            S                      ⁢                                                                                          ⁢                                              H                        ⁡                                                  (                          1                          )                                                                                      +                    …                    +                                          S                      ⁢                                                                                          ⁢                                              H                        ⁡                                                  (                          N                          )                                                                                                      )                                                                                                        =                            ⁢                                                σ                  ·                  M                                ⁢                                                                  ⁢                S                ⁢                                                                  ⁢                K                                                                        (        1        )            
On the other hand, if the reconstruction processing is executed with the results of the same linear operation CALC for individual shares, using the shares SH(1) to SH(N) and independent values σ(1) to σ(N) as operands, the results being shares SH′(1) to SH′(N), the result of the operation using the secret information MSK as an operand cannot be obtained usually. If the reconstruction processing is executed with SH′(1)=σ(1)·SH(1), . . . , SH′(N)=σ(N)·SH(N) as the shares SH′(1), . . . , SH′(N), the following can be obtained, for example.σ(1)·SH(1)+ . . . +σ(N)·SH(N)  (2)
[(K, N) Threshold Secret Sharing Scheme]
In a (K, N) threshold secret sharing scheme, if any K different shares SH(φ1) to SH(φK) are given, the secret information MSK can be reconstructed, whereas if any (K−1) shares SH(φ1) to SH(φK−1) are given, the secret information MSK can never be obtained. An example is given below.                A (K−1)-th degree polynomial f(x)=ξ0+ξ1·x+ξ2·x2+ . . . +ξK−1·xK−1 that satisfies f(0)=MSK is selected at random. That is, ξ0=MSK is specified, and ξ1 to ξK−1 are selected at random. The shares are given by SHρ=(ρ, f(ρ)) (ρ=1 to N).        If any K different shares SH(φ1) to SH(φK) ((φ1, . . . , φK)⊂(1, . . . , N)) are obtained, the secret information MSK can be reconstructed by the following reconstruction processing, using Lagrange's interpolation Expression, for example.        
                              M          ⁢                                          ⁢          S          ⁢                                          ⁢          K                =                              f            ⁡                          (              0              )                                =                                                    λ                1                            ·                              f                ⁡                                  (                                      φ                    1                                    )                                                      +            …            +                                          λ                K                            ·                              f                ⁡                                  (                                      φ                    K                                    )                                                                                        (        3        )                                                      λ            ρ                    ⁡                      (            x            )                          =                                                            (                                  x                  -                                      ϕ                    1                                                  )                            ⁢                                                          ⁢                              …                ⁢                                                                  ⁢                                  ⋁                  ρ                                ⁢                                                                  ⁢                …                            ⁢                                                          ⁢                              (                                  x                  -                                      ϕ                    K                                                  )                                                                    (                                                      ϕ                    ρ                                    -                                      ϕ                    1                                                  )                            ⁢                                                          ⁢                              …                ⁢                                                                  ⁢                                  ⋁                  ρ                                ⁢                                                                  ⁢                …                            ⁢                                                          ⁢                              (                                                      ϕ                    ρ                                    -                                      ϕ                    K                                                  )                                              ∈                      F            q                                              (        4        )            
Here, the symbol  indicates that the ρ-th operand [element (φρ−φρ) of the denominator, element (x−φρ) of the numerator] from the beginning is not present. The denominator of Expression (4) is(φρ−φρ1)· . . . ·(φρ−φρ−1)·(φρ−φρ+1)· . . . ·(φρ−φK)and the numerator of Expression (4) is(x−φ1)· . . . ·(x−φρ−1)·(x−φρ+1)· . . . ·(x−φK)These relationships hold on the field.
The operation of Expression (3) is linear. A value reconstructed with the results of the same linear operation CALC for individual shares, using the shares SH(φ1) to SH(φK) and the value σ as operands, the results being shares SH′(φ1) to SH′(φK), becomes equal to the result of the linear operation CALC using the secret information MSK and the value σ as operands. If a value is reconstructed with the results of the same linear operation CALC for the individual shares using the shares SH(φ1) to SH(φK) and independent values σ(φ1) to (φK) as operands, the results being shares SH′(φ1) to SH′(φK), the result of the operation using the secret information MSK as an operand cannot be obtained usually.